package com.leetcode.algorithm.y22.m07.w4;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 56. 合并区间
 * 
 * https://leetcode.cn/problems/merge-intervals/
 * 
 * @author jie.deng
 *
 */
class Question0056Solution01 {
	
	public int[][] merge(int[][] intervals) {
		PriorityQueue<int[]> queue = new PriorityQueue<>((arr1, arr2) -> arr1[0] - arr2[0]);
		for (int[] interval : intervals) {
			queue.offer(interval);
		}

		int[][] ret = new int[intervals.length][2];
		int idx = 0;
		while (!queue.isEmpty()) {
			int[] arr = queue.poll();
			int left = arr[0];
			int right = arr[1];
			while (!queue.isEmpty()) {
				int[] tmp = queue.peek();
				if (tmp[0] > right) {
					break;
				}
				queue.poll();
				right = Math.max(right, tmp[1]);
			}
			ret[idx++] = new int[] { left, right };
		}

		return Arrays.copyOfRange(ret, 0, idx);
	}
    
}